package com.ljy.my_study.lintcode.K数之和;

import java.util.HashSet;
import java.util.Set;

/** 
* @author James
* @date 2018年9月30日 
*/
public class TestMain4 {
//	描述
//	给定 n 个不同的正整数，整数 k（k <= n）以及一个目标数字 target。　
//	在这 n 个数里面找出 k 个数，使得这 k 个数的和等于目标数字，求问有多少种方案？
//
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	给出 [1,2,3,4]，k=2， target=5，[1,4] 和 [2,3] 是 2 个符合要求的方案，返回 2。
	public static void main(String[] args) {
//		int[] nums= {1,3,4,5,6,8,11,14,16,19,20,23,25,28,30,33,34,36,39,41,43,45,46,48,51,53,55,56,58,59,60};
//		System.out.println(kSum(nums,26,811));
		int[] nums= {1,3,4,5,8,10,11,12,14,17,20,22,24,25,28,30,31,34,35,37,38,40,42,44,45,48,51,54,56,59,60,61,63,66};
		System.out.println(kSum(nums,24,842));
//		int[] nums= {1,4,7,9,10,12,15,18,20,21,22,25,28,31,33,36,38,39,41,43,44,45,48,50,53};
//		System.out.println(kSum(nums,21,617));
//		int[] nums= {1,2,3,4,5,6,7};
//		System.out.println(kSum(nums,4,12));
	}
	
	public static int kSum(int[] arr, int k, int target) {
        // write your code here
        int n = arr.length;
        int num = 0 ;

        if (k<0||k>n){
            return num;
        }
        int[][] f = new int[k+1][target+1];
        f[0][0] = 1;
        //使用i-1的原因，是因为这里把三维数组合并成了二维数组
        //f[i][k][target] = f[i-1][k][target] + f[i-1][k-1][target-arr[i]]
        for (int i = 0; i < n; i++){
            for (int j = k ; j >= 1;j--){
                for (int s = target ; s >= arr[i] ; s--){
                    f[j][s] = f[j][s]+f[j-1][s-arr[i]];
                }
            }
        }
        return f[k][target];
    }

}
